package cs340.stormtroopers.hypeerweb;

import java.util.Collection;
import java.util.HashSet;
import java.util.ArrayList;

/**
 * Represents a Node in a HyPeerWeb. <br/>
 * <br/>
 * 
 * <pre>
 * <b>Instance Domain:</b>
 * 		connections : Connections
 * 		webId       : WebId
 * 		state       : NodeState
 * <b>Instance Invariants:</b>
 * 		webId is a non-null valid WebId (id >= -1)
 * 		state is always non-null and correctly represents the node's actual state
 * 			- if node is end cap node, state is EndCapNode
 * 			- otherwise, if node has down pointers, state is DownPointingNode
 * 			- otherwise, state is NormalNode
 * 		connections is a non-null valid Connections object valid for the Node's webId
 * 			- neighbors differ by one bit in their webIds
 * 			- the fold's webId is the complement of the Node's webId
 * 			- etc.
 * </pre>
 * 
 * @author Andy Morrow
 * @author Brad Spendlove
 * @author Daniel Howard
 * @author James Gurr
 * @author William Highland
 * 
 */

public class Node
{
	/**
	 * Singleton to implement the null object pattern. One and only null Node.
	 */
	public static final NullNode NULL_NODE = new NullNode();

	/**
	 * The node's current WebId.
	 */
	private WebId webId;
	/**
	 * The node's list of connections.
	 */
	private Connections connections;
	/**
	 * The node's current state.
	 */
	private NodeState state;

	// ///////////////////////////////////////////////////////// CONSTRUCTORS
	/**
	 * Sets local variables correctly for a null node.
	 * 
	 * @pre None.
	 * @post The node is configured as a null node.
	 */
	private void invalid()
	{
		int newWebId = -1;
		int height = -1;
		this.webId = new WebId(newWebId, height);

		ArrayList<Node> neighborsBiggerThanMe = new ArrayList<Node>();
		ArrayList<Node> childlessNeighborsSmallerThanMe = new ArrayList<Node>();
		ArrayList<Node> parentNeighborsSmallerThanMe = new ArrayList<Node>();
		ArrayList<Node> upPointers = new ArrayList<Node>();
		ArrayList<Node> downPointers = new ArrayList<Node>();
		Node fold = NULL_NODE;
		Node surrogateFold = NULL_NODE;
		Node inverseSurrogateFold = NULL_NODE;
		connections = new Connections(neighborsBiggerThanMe,
				childlessNeighborsSmallerThanMe, parentNeighborsSmallerThanMe,
				upPointers, downPointers, fold, surrogateFold,
				inverseSurrogateFold);

		state = NormalNode.getSingleton();
	}

	/**
	 * Public constructor creates a node with the given webId.
	 * 
	 * @param webId
	 *            the new WebId's integer value
	 * @pre webId >= 0
	 * @post The node is correctly configured with the new WebId and with empty
	 *       neighbor and surrogate neighbor lists.<br>
	 *       The node is its own fold.
	 */
	public Node(int webId)
	{
		if (webId >= 0)
		{
			this.webId = new WebId(webId);
			ArrayList<Node> neighborsBiggerThanMe = new ArrayList<Node>();
			ArrayList<Node> childlessNeighborsSmallerThanMe = new ArrayList<Node>();
			ArrayList<Node> parentNeighborsSmallerThanMe = new ArrayList<Node>();
			ArrayList<Node> upPointers = new ArrayList<Node>();
			ArrayList<Node> downPointers = new ArrayList<Node>();
			Node fold = this;
			Node surrogateFold = NULL_NODE;
			Node inverseSurrogateFold = NULL_NODE;
			connections = new Connections(neighborsBiggerThanMe,
					childlessNeighborsSmallerThanMe,
					parentNeighborsSmallerThanMe, upPointers, downPointers,
					fold, surrogateFold, inverseSurrogateFold);

			updateState();
		}
		else
		{
			invalid();
		}
	}

	/**
	 * Public constructor creates a new node with the given WebId and height.
	 * 
	 * @param webId
	 *            the integer value of the new WebId
	 * @param height
	 *            the number of significant bits or height of the WebId
	 * @pre webId >= 0 AND<br>
	 *      height <= 31 Note that in this implementation we use 32 bit
	 *      integers; thus the restriction on height. AND<br>
	 *      height >= the index of the highest significant bit in webId
	 * @post The node is correctly configured with the new WebId and with empty
	 *       neighbor and surrogate neighbor lists. AND<br>
	 *       The node is its own fold.
	 */
	public Node(int webId, int height)
	{
		if (webId >= 0 && height <= 31
				&& height >= WebId.locationOfMostSignificantOneBit(webId) + 1)
		{
			this.webId = new WebId(webId, height);
			ArrayList<Node> neighborsBiggerThanMe = new ArrayList<Node>();
			ArrayList<Node> childlessNeighborsSmallerThanMe = new ArrayList<Node>();
			ArrayList<Node> parentNeighborsSmallerThanMe = new ArrayList<Node>();
			ArrayList<Node> upPointers = new ArrayList<Node>();
			ArrayList<Node> downPointers = new ArrayList<Node>();
			Node fold = this;
			Node surrogateFold = NULL_NODE;
			Node inverseSurrogateFold = NULL_NODE;
			connections = new Connections(neighborsBiggerThanMe,
					childlessNeighborsSmallerThanMe,
					parentNeighborsSmallerThanMe, upPointers, downPointers,
					fold, surrogateFold, inverseSurrogateFold);

			updateState();
		}
		else
		{
			invalid();
		}
	}

	/**
	 * Copy constructor.
	 * 
	 * @param other
	 *            a valid Node to copy
	 * @pre other != NULL_NODE and is a valid node
	 * @post the new Node is an exact and complete deep copy of other
	 */
	public Node(Node other)
	{
		int newWebId = other.webId.getValue();
		int newHeight = other.webId.getHeight();
		this.webId = new WebId(newWebId, newHeight);

		// Copy all node connections to this node
		Connections otherConnections = other.getConnections();
		ArrayList<Node> neighborsBiggerThanMe = new ArrayList<Node>(
				otherConnections.getNeighborsBiggerThanMe());
		ArrayList<Node> childlessNeighborsSmallerThanMe = new ArrayList<Node>(
				otherConnections.getChildlessNeighborsSmallerThanMe());
		ArrayList<Node> parentNeighborsSmallerThanMe = new ArrayList<Node>(
				otherConnections.getParentNeighborsSmallerThanMe());
		ArrayList<Node> upPointers = new ArrayList<Node>(
				otherConnections.getUpPointers());
		ArrayList<Node> downPointers = new ArrayList<Node>(
				otherConnections.getDownPointers());

		Node fold = otherConnections.getFold();
		Node surrogateFold = otherConnections.getSurrogateFold();
		Node inverseSurrogateFold = otherConnections.getInverseSurrogateFold();

		connections = new Connections(neighborsBiggerThanMe,
				childlessNeighborsSmallerThanMe, parentNeighborsSmallerThanMe,
				upPointers, downPointers, fold, surrogateFold,
				inverseSurrogateFold);

		updateState();
	}

	/**
	 * Returns a string representation of this node.
	 * 
	 * @pre None
	 * @post Returns a string representation of this node.
	 */
	public String toString()
	{
		return "" + webId.getValue();
	}

	// //////////////////////////////////////////////////////////// PUBLIC
	// GETTERS / SETTERS

	/**
	 * Gets the list of down-pointers (surrogate neighbors).
	 * 
	 * @return list of down-pointers (surrogate neighbors)
	 */
	public ArrayList<Node> getDownPointers()
	{
		return connections.getDownPointers();
	}

	/**
	 * Sets the list of down-pointers (surrogate neighbors).
	 * 
	 * @param newDownPointers
	 *            List of nodes to point to.
	 * @pre newDownPointers != null
	 * @post the node's list of down-pointers is a complete deep copy of
	 *       newDownPointers
	 */
	private void setDownPointers(ArrayList<Node> newDownPointers)
	{
		connections.setDownPointers(newDownPointers);
		updateState();
	}

	/**
	 * Adds a down-pointer to the list.
	 * 
	 * @param downPointer
	 *            a node to point to
	 * @post The new Node is inserted in the correct order into the
	 *       down-pointers list.
	 */
	public void addDownPointer(Node downPointer)
	{
		connections.addDownPointer(downPointer);
		updateState();
	}

	/**
	 * Removes a down-pointer.
	 * 
	 * @param downPointer
	 *            a node to remove from the down-pointers list
	 * @pre downPointer != null AND<br>
	 *      downPointer is a member of this Node's list of down-pointers
	 * @post downPointer is no longer in this Node's list of down-pointers
	 */
	public void removeDownPointer(Node downPointer)
	{
		connections.removeDownPointer(downPointer);
		updateState();
	}

	/**
	 * Adds a neighbor.
	 * 
	 * @param neighbor
	 *            a Node to add as a neighbor
	 * @pre neighbor is not already in the Node's neighbor list AND<br>
	 *      neighbor != null AND<BR>
	 *      neighbor.webId is a neighbor to this Node's webId
	 * @post neighbor is inserted in the correct order into the list of
	 *       neighbors.
	 */
	public void addNeighbor(Node neighbor)
	{
		// assumption: this is only called from within a valid web
		// TODO make sure this works
		connections.addNeighbor(neighbor);
	}

	/**
	 * Returns a complete list of this node's neighbors.
	 * 
	 * @return a complete list of this node's neighbors.
	 */
	public ArrayList<Node> getNeighbors()
	{
		ArrayList<Node> neighbors = new ArrayList<Node>(
				connections.getNeighbors());

		return neighbors;
	}

	/**
	 * Sets all the neighbors of this node.
	 * 
	 * @param parentsSmaller
	 *            a list of neighbor nodes who have children and have webids
	 *            smaller than this node
	 * @param childlessSmaller
	 *            a list of neighbor nodes who do not have children and have
	 *            webids smaller than this node
	 * @param bigger
	 *            a list of neighbor nodes whose webids are bigger than this
	 *            node
	 * @pre The three lists of valid lists of neighbors.
	 * @post The Node's neighbors are updated with deep copies of these lists.
	 */
	private void setNeighbors(ArrayList<Node> parentsSmaller,
			ArrayList<Node> childlessSmaller, ArrayList<Node> bigger)
	{
		connections.setParentNeighborsSmallerThanMe(parentsSmaller);
		connections.setChildlessNeighborsSmallerThanMe(childlessSmaller);
		connections.setNeighborsBiggerThanMe(bigger);
	}

	/**
	 * Adds an up-pointer.
	 * 
	 * @param upPointer
	 *            a node to point to
	 * @pre upPointer is a valid up-pointer for this node as defined by its
	 *      webid
	 * @post upPointer is inserted into the Node's list of uppointers in the
	 *       correct order.
	 */
	public void addUpPointer(Node upPointer)
	{
		connections.addUpPointer(upPointer);
	}

	/**
	 * Sets all the up-pointers.
	 * 
	 * @param newUpPointers
	 *            a list of Nodes to point up to
	 * @pre All the nodes in the list are valid up-pointers for this node
	 * @post this node now points at all the given nodes
	 */
	private void setUpPointers(ArrayList<Node> newUpPointers)
	{
		connections.setUpPointers(newUpPointers);
	}

	/**
	 * Returns all the up-pointers
	 * 
	 * @return a list of all the nodes this node points up to
	 */
	public ArrayList<Node> getUpPointers()
	{
		return connections.getUpPointers();
	}

	/**
	 * Creates a simplified node domain to be used in testing.
	 * 
	 * @return a SimplifiedNodeDomain representing this node exactly
	 * @pre this node is valid = no null connections or null lists - only
	 *      NULL_NODE and empty lists allowed
	 * @post the SimplifiedNodeDomain returned is valid and correctly represents
	 *       this node
	 */
	public SimplifiedNodeDomain constructSimplifiedNodeDomain()
	{
		HashSet<Integer> neighborInts = new HashSet<Integer>();
		for (Node n : getNeighbors())
			neighborInts.add(n.getWebIdValue());

		HashSet<Integer> upPointerInts = new HashSet<Integer>();
		for (Node n : getUpPointers())
			upPointerInts.add(n.getWebIdValue());

		HashSet<Integer> downPointerInts = new HashSet<Integer>();
		for (Node n : getDownPointers())
			downPointerInts.add(n.getWebIdValue());

		int foldInt, surrogateFoldInt, inverseSurrogateFoldInt;

		Node fold = getFold();
		foldInt = fold.getWebIdValue();

		Node surrogateFold = getSurrogateFold();
		surrogateFoldInt = surrogateFold.getWebIdValue();

		Node inverseSurrogateFold = getInverseSurrogateFold();
		inverseSurrogateFoldInt = inverseSurrogateFold.getWebIdValue();

		return new SimplifiedNodeDomain(webId.getValue(), webId.getHeight(),
				neighborInts, upPointerInts, downPointerInts, foldInt,
				surrogateFoldInt, inverseSurrogateFoldInt, state.getStateId());
	}

	/**
	 * Gets the connections object associated with thisNode
	 * 
	 * @return the complete Connections object for this node's connections
	 */
	public Connections getConnections()
	{
		return connections;
	}

	/**
	 * Gets the connections its child node will have upon insertion into the
	 * HyPeerWeb.
	 * 
	 * @return Connections objects with correct connections for its child
	 */
	public Connections getChildConnections()
	{
		// this is from my class notes: "child's fold is parent's old fold,
		// unless parent has an invSurrFold
		Node childfold;
		if (getInverseSurrogateFold() != NULL_NODE)
			childfold = getInverseSurrogateFold();
		else
			childfold = getFold();

		ArrayList<Node> blankList = new ArrayList<Node>();

		ArrayList<Node> listWithThis = new ArrayList<Node>(1);
		listWithThis.add(this);

		ArrayList<Node> upPointers = new ArrayList<Node>(
				connections.getUpPointers());
		ArrayList<Node> neighborsBiggerThanMe = new ArrayList<Node>(
				connections.getNeighborsBiggerThanMe());
		Connections childConnections = new Connections(blankList, // neighborsBiggerThanMe
				upPointers, // childlessNeighborsSmallerThanMe
				listWithThis, // parentNeighborsSmallerThanMe
				blankList, // upPointers
				neighborsBiggerThanMe, // downPointers
				childfold, // fold
				NULL_NODE, // surrogateFold
				NULL_NODE // inverseSurrogateFold
		);

		return childConnections;
	}

	/**
	 * Returns the WebId of the Node.
	 * 
	 * @return the WebId
	 */
	public WebId getWebId()
	{
		return webId;
	}

	/**
	 * Returns the integer value of the Node's WebId.
	 * 
	 * @return the WebId as an integer
	 */
	public int getWebIdValue()
	{
		return webId.getValue();
	}

	/**
	 * Removes a neighbor from this Node's list.
	 * 
	 * @param neighbor
	 *            Node to be removed
	 * @pre The neighbor parameter is a Node which is already in this Node's
	 *      list of neighbors
	 * @post The node is no longer in this Node's list of neighbors AND<br>
	 *       the other neighbors are unaffected.
	 */
	public void removeNeighbor(Node neighbor)
	{
		// TODO check assumptions
		// assumption: only used from within a valid web
		connections.removeNeighbor(neighbor);
	}

	/**
	 * Removes an up-pointer (inverse surrogate neighbor) from this Node's list.
	 * 
	 * @param upPointer
	 *            the Node to be removed
	 * @pre the Node to be removed is an inverse surrogate neighbor of this Node
	 * @post the Node to be removed is no longer in this Node's list of
	 *       up-pointers AND<br>
	 *       the other up-pointers remain unaffected.
	 */
	public void removeUpPointer(Node upPointer)
	{
		connections.removeUpPointer(upPointer);
	}

	/**
	 * Resets all of the connections for this Node.
	 * 
	 * @param connections
	 *            the new set of connections
	 * @pre the passed Connections are valid and non-null
	 * @post this Node now has the given connections<br>
	 *       but does NOT update the nodes it now points to
	 */
	public void setConnections(Connections connections)
	{
		setNeighbors(connections.getParentNeighborsSmallerThanMe(),
				connections.getChildlessNeighborsSmallerThanMe(),
				connections.getNeighborsBiggerThanMe());
		setUpPointers(connections.getUpPointers());
		setDownPointers(connections.getDownPointers());
		setFold(connections.getFold());
		setSurrogateFold(connections.getSurrogateFold());
		setInverseSurrogateFold(connections.getInverseSurrogateFold());
	}

	/**
	 * Sets the fold of this Node
	 * 
	 * @param newFold
	 *            Node to point to
	 * @pre newFold is not NULL AND<br>
	 *      is in the same HyPeerWeb
	 * @post this Node now points to newFold as its fold
	 */
	public void setFold(Node newFold)
	{
		// setting surrogateFold to NULL_NODE is done by somebody else in
		// updateInsertionPoint
		connections.setFold(newFold);
	}

	/**
	 * Returns this Node's fold
	 * 
	 * @return the fold or the NULL_NODE
	 */
	public Node getFold()
	{
		return connections.getFold();
	}

	/**
	 * Sets this Node's inverse surrogate fold.
	 * 
	 * @param newInverseSurrogateFold
	 *            the Node to point to
	 * @pre the new Node is not null AND<br>
	 *      resides in the same HyPeerWeb
	 * @post this Node now points to the passed Node as its inverse surrogate
	 *       fold
	 */
	public void setInverseSurrogateFold(Node newInverseSurrogateFold)
	{
		connections.setInverseSurrogateFold(newInverseSurrogateFold);
	}

	/**
	 * Returns this Node's inverse surrogate fold.
	 * 
	 * @return the inverse surrogate fold or the NULL_NODE
	 */
	public Node getInverseSurrogateFold()
	{
		return connections.getInverseSurrogateFold();
	}

	/**
	 * Sets this Node's surrogate fold.
	 * 
	 * @param newSurrogateFold
	 *            the Node to point to
	 * @pre the Node to point to is non-null AND<br>
	 *      resides in the same HyPeerWeb
	 * @post this Node now points to the passed Node as its surrogate fold
	 */
	public void setSurrogateFold(Node newSurrogateFold)
	{
		connections.setSurrogateFold(newSurrogateFold);
	}

	/**
	 * Returns this Node's surrogate fold.
	 * 
	 * @return the surrogate fold or the NULL_NODE
	 */
	public Node getSurrogateFold()
	{
		return connections.getSurrogateFold();
	}

	/**
	 * Sets this node to have a new WebId.
	 * 
	 * @param webId
	 *            the new WebId
	 * @pre the new WebId is non-null AND<br>
	 *      the new WebId is consistent (valid height for value etc.) AND<br>
	 *      the new WebId is valid in the current web
	 * @post this Node has the new WebId AND<br>
	 *       has updated its internal state accordingly
	 */
	public void setWebId(WebId webId)
	{
		this.webId = webId;
		updateState();
	}

	/**
	 * Prints the value of the fold or surrogate fold.<br>
	 * Mainly for debugging.
	 * 
	 * @pre this Node's fold is non-null OR<br>
	 *      this Node's surrogate fold is non-null
	 * @post the correct WebId has been printed to the terminal
	 */
	public void printFold()
	{
		if (connections.getFold() != null)
		{
			Node fold = connections.getFold();
			System.out.println("Node " + webId.getValue() + "'s fold is "
					+ fold.getWebIdValue());
		}
		else
		{
			Node surrogateFold = connections.getSurrogateFold();
			System.out.println("Node " + webId.getValue()
					+ "'s surrage fold is " + surrogateFold.getWebIdValue());
		}
	}

	// /////////////////////////////////////////////////////// ADDING NODES

	/**
	 * Adds a node to the HyPeerWeb that this Node belongs to.
	 * 
	 * @param newNode
	 *            the Node to add to the HyPeerWeb
	 * @pre This Node is a member of a HyPeerWeb AND<br>
	 *      the other Node is not already a member of the same HyPeerWeb AND<br>
	 *      the other Node is in a valid, consistent state
	 * @post The other Node is now a member of the HyPeerWeb AND<br>
	 *       it has been inserted as the highest Node in the web (IE it has the
	 *       greatest WebId) AND<br>
	 *       the other Nodes in the HyPeerWeb have been updated to point toward
	 *       it AND<br>
	 *       the total size of the HyPeerWeb has increased by one
	 */
	public void addToHyPeerWeb(Node newNode)
	{
		Node insertionPoint = this.findEndCapNode().findInsertionPoint();
		newNode.setWebId(insertionPoint.getWebId().createChildsWebId());
		newNode.setConnections(insertionPoint.getChildConnections());

		newNode.updateNewNodesAssociates();
		insertionPoint.updateInsertionPoint();
		insertionPoint.addNeighbor(newNode);
		insertionPoint.updateState();
		newNode.updateState();
		// This has to be done here because:
		// sometimes we call addToHyPeerWeb() on the HyPeerWeb singleton
		// sometimes we call addToHyPeerWeb() directly on a node
		// in both cases, the node to be added must be added to the HyPeerWeb's
		// set
		// so we do it here instead of in HyPeerWeb to guarantee it will always
		// happen
		HyPeerWeb.getSingleton().addNode(newNode);
	}

	private void updateInsertionPoint()
	{
		// notes: parent's new surrFold is its old fold
		if (getWebIdValue() == 0 && getFold().getWebIdValue() == 1
				&& getFold().getFold().getWebIdValue() == getWebIdValue())
		{
			// no op
		}
		else if (getInverseSurrogateFold() == NULL_NODE)
		{
			setSurrogateFold(getFold());
			setFold(NULL_NODE);
			getSurrogateFold().setInverseSurrogateFold(this);
		}
		else
		{
			getInverseSurrogateFold().setSurrogateFold(NULL_NODE);
			setInverseSurrogateFold(NULL_NODE);
		}

		// No longer an surrogate neighbor, so removing self from up pointer's
		// down pointers
		for (Node inverseSurrogateNeighbor : connections.getUpPointers())
			inverseSurrogateNeighbor.removeDownPointer(this);
		connections.clearUpPointers();

		webId.setHeight(webId.getHeight() + 1);

		for (Node neighbor : connections.getNeighborsBiggerThanMe())
			neighbor.neighborHadChild(this);
	}

	private void updateNewNodesAssociates()
	{
		for (Node neighbor : connections.getChildlessNeighborsSmallerThanMe())
			neighbor.addNeighbor(this);

		for (Node surrogateNeighbor : connections.getDownPointers())
			surrogateNeighbor.addUpPointer(this);

		connections.getFold().setFold(this);
	}

	// assumptions: neighbor is a real neighbor of this node
	private void neighborHadChild(Node neighbor)
	{
		connections.neighborHadChild(neighbor);
	}

	private Node findSmallestChildlessNeighbor()
	{
		Node smallest = this;

		/*
		 * for (Node Current : getNeighbors()) if (current.getWebIdValue() <
		 * smallest.getWebIdValue() && current.getWebId().getHeight() ==
		 * webId.getHeight()) smallest = current;
		 */

		for (Node current : connections.getParentNeighborsSmallerThanMe())
			if (current.getWebIdValue() < smallest.getWebIdValue()
					&& current.getWebId().getHeight() == webId.getHeight())
				smallest = current;

		for (Node current : connections.getChildlessNeighborsSmallerThanMe())
			if (current.getWebIdValue() < smallest.getWebIdValue()
					&& current.getWebId().getHeight() == webId.getHeight())
				smallest = current;

		if (smallest.getWebIdValue() != getWebIdValue())
			return smallest.findSmallestChildlessNeighbor();
		else
			return this;

		/*
		 * return !childlessNeighborsSmallerThanMe.isEmpty() ?
		 * childlessNeighborsSmallerThanMe
		 * .get(0).findSmallestChildlessNeighbor() : this;
		 */
	}

	private Node findEndCapNode()
	{
		return fromMeToEndCapNode();
	}

	private Node findInsertionPoint()
	{
		return fromMeToInsertionPoint();
	}

	private Node fromMeToInsertionPoint()
	{
		return state.findInsertionPoint(this);
	}

	private Node fromMeToEndCapNode()
	{
		return state.findEndCapNode(this);
	}

	// //////////////////////////////////////////////////////////// REMOVING
	// NODES

	public void removeFromHyPeerWeb()
	{
		Node deletionPoint = findDeletionPoint();

		deletionPoint.removeSelf();
		HyPeerWeb.getSingleton().removeNode(deletionPoint);
		if (deletionPoint != this)
		{
			deletionPoint.takePlaceOf(this);
			// we'll hold off on this optimization until we know it all works
			// right
			// connections.clearAll();
		}

		// Corner case when there is only one node left in the web
		if (getNeighbors().size() == 0)
		{
			setFold(this);
			setSurrogateFold(NULL_NODE);
			setInverseSurrogateFold(NULL_NODE);
		}
	}

	private void removeSelf()
	{
		Node parent = findParent(); // WARNING! Look out for Null-Pointer

		new RemoveSelfFromNeighbors(this).execute(parent);
		new RemoveSelfAsUpPointer(this).execute(this);

		// for (Node neighbor : getNeighbors())
		// {
		// neighbor.removeNeighbor(this);
		// if (neighbor != parent)
		// {
		// neighbor.addDownPointer(parent);
		// parent.addUpPointer(neighbor);
		// }
		// }
		// for (Node down : getDownPointers())
		// down.removeUpPointer(this);

		if (parent.getFold() == NULL_NODE)
		{
			getFold().setFold(parent);
			parent.setFold(getFold());
			parent.getInverseSurrogateFold().setInverseSurrogateFold(NULL_NODE);
			parent.setSurrogateFold(NULL_NODE);
			parent.getFold().setInverseSurrogateFold(NULL_NODE);
		}
		else
		{
			getFold().setFold(NULL_NODE);
			getFold().setSurrogateFold(parent);
			parent.setInverseSurrogateFold(getFold());
			parent.getFold().setInverseSurrogateFold(NULL_NODE);
		}

		// We should only need to update parent's height
		parent.webId.setHeight(parent.webId.getHeight() - 1);
		parent.updateState();
	}

	private Node findParent()
	{
		// Quick and dirty solution
		/*
		 * Potential time saver: return parentNeighborsSmallerThanMe.get(0);
		 */
		int parentId = webId.getParentsValue();

		for (Node neighbor : getNeighbors())
			if (neighbor.getWebIdValue() == parentId)
				return neighbor;
		return null;
	}

	private void takePlaceOf(Node leavingNode)
	{
		webId = leavingNode.getWebId();

		// uses the Null object pattern
		// that's why we can set ourselves as the fold of the fold, sf, and isf
		setConnections(leavingNode.getConnections());

		connections.getFold().setFold(this);
		connections.getSurrogateFold().setInverseSurrogateFold(this);
		connections.getInverseSurrogateFold().setSurrogateFold(this);

		for (Node neighbor : connections.getNeighbors())
			neighbor.connections.replaceNeighbor(leavingNode, this);

		for (Node down : connections.getDownPointers())
			down.connections.replaceUpPointer(leavingNode, this);

		for (Node up : connections.getUpPointers())
			up.connections.replaceDownPointer(leavingNode, this);

		state = leavingNode.state;
	}

	// Andy's alg:
	// Find end cap node, take it's fold. follow to largest neighbor

	public Node findDeletionPoint()
	{
		Node start = findEndCapNode();
		// if(start.fold.getWebIdValue()==0)
		// return start;
		start = start.getConnections().getFold();
		return start.followBiggestNeighbor();
	}

	private Node followBiggestNeighbor()
	{
		Node biggest = this;
		for (Node n : getNeighbors())
			if (n.getWebIdValue() > biggest.getWebIdValue())
				biggest = n;
		if (biggest.getWebIdValue() == webId.getValue())
			return biggest;
		else
			return biggest.followBiggestNeighbor();
	}

	// ////////////////////////////////////////////////////////////////////
	// STATES

	private void updateState()
	{
		if (Math.pow(2, webId.getHeight()) - 1 == webId.getValue())
			state = EndCapNode.getSingleton();
		else if (!getDownPointers().isEmpty())
			state = DownPointingNode.getSingleton();
		else
			state = NormalNode.getSingleton();
	}

	public static class NormalNode extends NodeState
	{
		public static int STATE_ID = 0;

		public int getStateId()
		{
			return STATE_ID;
		}

		private static NormalNode singleton = null;

		private NormalNode()
		{
		}

		public Node findInsertionPoint(Node node)
		{
			return node.findSmallestChildlessNeighbor();
		}

		public Node findEndCapNode(Node node)
		{
			Node largestNeighbor = new Node(0);
			for (Node n : node.getConnections().getNeighborsBiggerThanMe())
				if (n.getWebIdValue() > largestNeighbor.getWebIdValue())
					largestNeighbor = n;
			return largestNeighbor.fromMeToEndCapNode();
		}

		public static NormalNode getSingleton()
		{
			if (singleton == null)
				singleton = new NormalNode();
			return singleton;
		}

	}

	public static class DownPointingNode extends NodeState
	{
		public static int STATE_ID = 1;

		public int getStateId()
		{
			return STATE_ID;
		}

		private static DownPointingNode singleton = null;

		private DownPointingNode()
		{
		}

		public Node findInsertionPoint(Node node)
		{
			return node.findSmallestChildlessNeighbor();
		}

		public Node findEndCapNode(Node node)
		{
			Node largestDownPointer = new Node(0);
			for (Node n : node.getConnections().getDownPointers())
				if (n.getWebIdValue() > largestDownPointer.getWebIdValue())
					largestDownPointer = n;
			return largestDownPointer.fromMeToEndCapNode();
		}

		public static DownPointingNode getSingleton()
		{
			if (singleton == null)
				singleton = new DownPointingNode();
			return singleton;
		}

	}

	public static class EndCapNode extends NodeState
	{
		public static int STATE_ID = 2;

		public int getStateId()
		{
			return STATE_ID;
		}

		private static EndCapNode singleton = null;

		private EndCapNode()
		{
		}

		public Node findEndCapNode(Node node)
		{
			return node;
		}

		public Node findInsertionPoint(Node node)
		{
			if (node.getFold().webId.getValue() == 0)
				return node.getFold();

			else
				return node.findSmallestChildlessNeighbor();
		}

		public static EndCapNode getSingleton()
		{
			if (singleton == null)
				singleton = new EndCapNode();
			return singleton;
		}

	}

	// //////////////////////////////////////////////////// Template Pattern
	private class RemoveSelfFromNeighbors extends Operation
	{

		public RemoveSelfFromNeighbors(Node container)
		{
			super(container);
		}

		public Collection<Node> getCollection()
		{
			return container.getNeighbors();
		}

		public void appropriateOperation(Node neighbor, Node parent)
		{
			neighbor.removeNeighbor(container);
			if (neighbor != parent)
			{
				neighbor.addDownPointer(parent);
				parent.addUpPointer(neighbor);
			}
		}
	}

	private class RemoveSelfAsUpPointer extends Operation
	{

		public RemoveSelfAsUpPointer(Node container)
		{
			super(container);
		}

		@Override
		public Collection<Node> getCollection()
		{
			return container.getDownPointers();
		}

		@Override
		public void appropriateOperation(Node down, Node target)
		{
			down.removeUpPointer(target);
		}

	}
}